-- /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  */
-- /* GeoHash encoding/decoding and associated functions   (c) Chris Veness 2014-2016 / MIT Licence  */
-- /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  */

-- /**
--  * GeoHash encode, decode, bounds, neighbours.
--  *
--  * @namespace
--  */

GeoHash = {};

-- /* (GeoHash-specific) Base32 map */
GeoHash.base32 = '0123456789bcdefghjkmnpqrstuvwxyz';

-- /**
--  * Encodes latitude/longitude to geohash, either to specified precision or to automatically
--  * evaluated precision.
--  *
--  * @param   {number} lat - Latitude in degrees.
--  * @param   {number} lon - Longitude in degrees.
--  * @param   {number} [precision] - Number of characters in resulting geohash.
--  * @returns {string} GeoHash of supplied latitude/longitude.
--  * @throws  Invalid geohash.
--  *
--  * @example
--  *     var geohash = GeoHash.encode(52.205, 0.119, 7); // geohash: 'u120fxw'
--  */
function GeoHash.encode(lat, lon, precision)
    -- infer precision?
    if not precision then
        -- refine geohash until it matches precision of supplied lat/lon
        for p = 1, 12 do
            local hash = GeoHash.encode(lat, lon, p);
            local posn = GeoHash.decode(hash);
            if (posn.lat==lat and posn.lon==lon) then
                return hash;
            end
        end
        precision = 12; -- set to maximum
    end

    lat = tonumber(lat);
    lon = tonumber(lon);
    precision = tonumber(precision);

    if lat == 0 or lon == 0 or precision == 0 then
        return "";
    end

    local idx = 0;  -- index into base32 map
    local bit = 0;  --  each char holds 5 bits
    local evenBit = true;
    local geohash = '';

    local latMin =  -90;
    local latMax =  90;
    local lonMin = -180;
    local lonMax = 180;

    while (#geohash < precision) do
        if (evenBit) then
            -- bisect E-W longitude
            local lonMid = (lonMin + lonMax) / 2;
            if (lon >= lonMid) then
                idx = idx*2 + 1;
                lonMin = lonMid;
            else
                idx = idx*2;
                lonMax = lonMid;
            end
        else
            -- bisect N-S latitude
            local latMid = (latMin + latMax) / 2;
            if (lat >= latMid) then
                idx = idx*2 + 1;
                latMin = latMid;
            else
                idx = idx*2;
                latMax = latMid;
            end
        end
        evenBit = not evenBit;

        bit = bit + 1
        if (bit == 5) then
            -- 5 bits gives us a character: append it and start over
            geohash = geohash .. string.char(string.byte(GeoHash.base32 ,idx + 1));
            bit = 0;
            idx = 0;
        end
    end

    return geohash;
end

-- /**
--  * Decode geohash to latitude/longitude (location is approximate centre of geohash cell,
--  *     to reasonable precision).
--  *
--  * @param   {string} geohash - GeoHash string to be converted to latitude/longitude.
--  * @returns {{lat:number, lon:number}} (Center of) geohashed location.
--  * @throws  Invalid geohash.
--  *
--  * @example
--  *     var latlon = GeoHash.decode('u120fxw'); // latlon: { lat: 52.205, lon: 0.1188 }
--  */
function GeoHash.decode (geohash)
    local bounds = GeoHash.bounds(geohash); -- <-- the hard work
    -- now just determine the centre of the cell...

    local latMin = bounds.sw.lat;
    local lonMin = bounds.sw.lon;
    local latMax = bounds.ne.lat;
    local lonMax = bounds.ne.lon;

    -- cell centre
    local lat = (latMin + latMax)/2;
    local lon = (lonMin + lonMax)/2;

    -- round to close to centre without excessive precision: ⌊2-log10(Δ°)⌋ decimal places
    local pn1 = math.floor(2-math.log(latMax-latMin)/math.log(10));
    local pn2 = math.floor(2-math.log(lonMax-lonMin)/math.log(10));

    lat = tonumber(string.format("%."..pn1.."f", lat));
    lon = tonumber(string.format("%."..pn2.."f", lon));

    return { lat = tonumber(lat), lon = tonumber(lon) };
end

-- /**
--  * Returns SW/NE latitude/longitude bounds of specified geohash.
--  *
--  * @param   {string} geohash - Cell that bounds are required of.
--  * @returns {{sw: {lat: number, lon: number}, ne: {lat: number, lon: number}}}
--  * @throws  Invalid geohash.
--  */
function GeoHash.bounds(geohash)
    if #geohash== 0 then
        error('Invalid geohash');
    end

    geohash = string.lower(geohash);

    local evenBit = true;
    local latMin =  -90;
    local latMax =  90;
    local lonMin = -180;
    local lonMax = 180;

    for i = 1, #geohash do
        local chr = string.char(string.byte(geohash, i));
        local idx = string.find(GeoHash.base32, chr);
        if (idx == -1) then
            error('Invalid geohash');
        end

        idx = idx - 1;
        for n = 4, 0, -1 do
            local bitN = bit.band(bit.brshift(idx, n), 1);
            if (evenBit) then
                -- longitude
                local lonMid = (lonMin+lonMax) / 2;
                if (bitN == 1) then
                    lonMin = lonMid;
                else
                    lonMax = lonMid;
                end
            else
                -- latitude
                local latMid = (latMin+latMax) / 2;
                if (bitN == 1) then
                    latMin = latMid;
                else
                    latMax = latMid;
                end
            end
            evenBit = not evenBit;
        end
    end

    local bounds = {
        sw = { lat = latMin, lon = lonMin },
        ne = { lat = latMax, lon = lonMax },
    };

    return bounds;
end

-- /**
--  * Determines adjacent cell in given direction.
--  *
--  * @param   geohash - Cell to which adjacent cell is required.
--  * @param   direction - Direction from geohash (N/S/E/W).
--  * @returns {string} Geocode of adjacent cell.
--  * @throws  Invalid geohash.
--  */
function GeoHash.adjacent(geohash, direction)
    -- based on github.com/davetroy/geohash-js
    geohash = string.lower(geohash);
    direction = string.lower(direction);

    if #geohash == 0 then
        error('Invalid geohash');
    end

    if string.find('nsew', direction) == -1 then
        error('Invalid direction');
    end

    local neighbour = {
        n = { ["0"] = 'p0r21436x8zb9dcf5h7kjnmqesgutwvy', ["1"] = 'bc01fg45238967deuvhjyznpkmstqrwx' },
        w = { ["0"] = '238967debc01fg45kmstqrwxuvhjyznp', ["1"] = '14365h7k9dcfesgujnmqp0r2twvyx8zb' },
        e = { ["0"] = 'bc01fg45238967deuvhjyznpkmstqrwx', ["1"] = 'p0r21436x8zb9dcf5h7kjnmqesgutwvy' },
        s = { ["0"] = '14365h7k9dcfesgujnmqp0r2twvyx8zb', ["1"] = '238967debc01fg45kmstqrwxuvhjyznp' },
    };

    local border = {
        n = { ["0"] = 'prxz',     ["1"] = 'bcfguvyz' },
        s = { ["0"] = '028b',     ["1"] = '0145hjnp' },
        e = { ["0"] = 'bcfguvyz', ["1"] = 'prxz'     },
        w = { ["0"] = '0145hjnp', ["1"] = '028b'     },
    };

    local lastCh = string.char(string.byte(geohash, #geohash)); -- last character of hash
    local parent = string.sub(geohash, 1, #geohash-1); -- hash without last character

    local type = tostring(#geohash % 2);

    -- check for edge-cases which don't share common prefix
    if (string.find(border[direction][type], lastCh) ~= nil and parent ~= '') then
        parent = GeoHash.adjacent(parent, direction);
    end

    -- append letter for direction to parent
    return parent..string.char(string.byte(GeoHash.base32, string.find(neighbour[direction][type], lastCh)));
end


-- /**
--  * Returns all 8 adjacent cells to specified geohash.
--  *
--  * @param   {string} geohash - GeoHash neighbours are required of.
--  * @returns {{n,ne,e,se,s,sw,w,nw: string}}
--  * @throws  Invalid geohash.
--  */
function GeoHash.neighbours(geohash)
    return {
        n =  GeoHash.adjacent(geohash, 'n'),
        ne = GeoHash.adjacent(GeoHash.adjacent(geohash, 'n'), 'e'),
        e =  GeoHash.adjacent(geohash, 'e'),
        se = GeoHash.adjacent(GeoHash.adjacent(geohash, 's'), 'e'),
        s =  GeoHash.adjacent(geohash, 's'),
        sw = GeoHash.adjacent(GeoHash.adjacent(geohash, 's'), 'w'),
        w =  GeoHash.adjacent(geohash, 'w'),
        nw = GeoHash.adjacent(GeoHash.adjacent(geohash, 'n'), 'w'),
    };
end

return GeoHash;